Asynchronous Transfer Mode (ATM) includes a protocol for transmitting information over a network such as the Internet. ATM currently includes numerous standards that are publicly available. In ATM the flow of information, which may be referred to as traffic, may be specified as a number of cells transmitted per second. Cells are currently 53 byte sets of data that may be transmitted over an ATM link. Moreover, currently five of those 53 cell bytes are utilized to carry header information and the remaining 48 cell bytes are used to carry payload information that is being transmitted.
Modern networks may carry a variety of traffic, some of which may have strict timing requirements. With network protocols such as the ATM protocol, data traffic, including voice and video traffic, traverses a network via network devices such as ATM switches that assure that the appropriate connections are established, that the data reaches its destination via its designated connections, that bandwidth constraints are not exceeded and that timing requirements are met. Traffic flow through these network devices is often managed by a cell scheduler. In an ATM device such as an ATM switch, schedulers are used to manage the timing of cell transmission. Traffic with rigid timing requirements, such as real-time voice and video traffic must be accommodated in those schedulers along with other data traffic. The ATM protocol addresses those timing issues by designating special classes or categories of service for handling time sensitive data. ATM traffic thus generally has a quality of service (Qos) guarantee that varies depending on the specific requirements of the traffic type. Two classes of service that maintain end-to-end timing relationships across an ATM network are the constant bit rate (CBR) class of service and the variable bit rate real-time (VBR-rt) class of service, which are described in the ATM standards.
ATM cell schedulers generally include tables having slots that are populated according to the requirements of the traffic being scheduled such as CBR and VBR-rt along with other types of traffic having less demanding timing requirements. Thus, each cell to be transmitted may be identified in a slot of the table and the identified cells may be transmitted in the order in which they are identified in the table.
ATM traffic can enter and exit a network device such as a switch via one or more ports, with each port carrying a sub-stream of traffic. Certain of those sub-streams may furthermore be constant-bandwidth sub-streams and carry real-time traffic. Constant bandwidth sib-streams also adhere to timing requirements to assure constant bandwidth. To maintain proper timing in a scheduler table that sequentially runs through all slots in the table to find the next ATM cell to transmit, the distance between all consecutive table entries of a sub-stream of such real-time data should be equal. That distance between entries related to a sub-stream may be referred to as a step, may be measured in terms of a number of slots between entries for that sub-stream in the table, with each consecutive entry for a particular sub-stream of real-time data being a step apart, and may be referred to as Z.
When populating such a table with information from numerous sub-streams in accordance with timing requirements, the proper slots must be available and identified for population. Checking for slot availability generally becomes more laborious as more entries are made in the table and the table becomes more densely populated.